package com.zhuqi.linkedlist.doubly;


/**
 * <p>类描述</p>
 * Copyright: Copyright (C) 2023 YinTa, Inc. All rights reserved.
 * @author zhuqi
 * @since 2023/6/13 15:15
 */

public class DoublyLinkedList<T> {


	private Node<T> first;

	private Node<T> last;

	private int size;

	public DoublyLinkedList() {
		size = 0;
		first = null;
		last = null;
	}

	/**
	 * 头插
	 * @param data
	 */
	public void addFirst(T data) {
		Node<T> f = first;
		Node<T> node = new Node<>(data, null, f);
		if (first == null) {
			last = null;
		} else {
			f.prev = node;
			node.next = f;
		}
		first = node;
		size++;
	}

	/**
	 * 尾插
	 * @param data
	 */
	public void addLast(T data) {
		Node<T> l = last;
		Node<T> node = new Node<>(data, l, null);
		if (last == null) {
			first = node;
		} else {
			l.next = node;
			node.prev = l;
		}
		last = node;
		size++;
	}

	/**
	 * 根据元素找节点
	 * @param data data
	 * @return
	 */
	public Node<T> findNode(T data) {
		Node<T> firstPointer = first;
		Node<T> lastPointer = last;

		if (firstPointer == null || lastPointer == null) {
			return null;
		}

		int count = 0;
		int half = size % 2 == 0 ? size / 2 : size / 2 + 1;
		while (true) {
			if (count >= half) {
				break;
			}

			if (firstPointer.getData().equals(data)) {
				return firstPointer;
			} else {
				firstPointer = firstPointer.next;
			}

			if (lastPointer.getData().equals(data)) {
				return lastPointer;
			} else {
				lastPointer = lastPointer.prev;
			}
			count++;
		}
		return null;
	}

	/**
	 * 删除节点
	 * @param node
	 */
	public T removeNode(Node<T> node) {
		T data = node.data;
		Node<T> prev = node.prev;
		Node<T> next = node.next;
		if (prev == null) {
			first = next;
		} else {
			prev.next = next;
			node.prev = null;
		}

		if (next == null) {
			last = prev;
		} else {
			next.prev = prev;
			node.next = null;
		}

		node.data = null;
		size--;
		return data;
	}

	/**
	 * 获取当前元素个数
	 * @return
	 */
	public int size() {
		return size;
	}


	/**
	 * 获取下一个节点
	 */
	public Node<T> getNext(Node<T> node) {
		return node.next;
	}


	public Node getFirst() {
		return first;
	}


	public Node getLast() {
		return last;
	}


	@Override
	public String toString() {
		StringBuilder stringBuilder = new StringBuilder();
		Node node = this.getFirst();
		stringBuilder.append("{").append(node.toString());
		while ((node = this.getNext(node)) != null) {
			stringBuilder.append(", ").append(node.toString());
		}
		stringBuilder.append("}");
		return stringBuilder.toString();
	}

	public class Node<T> {

		public T data;

		public Node<T> prev;

		public Node<T> next;

		public Node(T data, Node<T> prev, Node<T> next) {
			this.data = data;
			this.prev = prev;
			this.next = next;
		}

		@Override
		public String toString() {
			return "Node{" + "data=" + data + '}';
		}

		public T getData() {
			return data;
		}

	}
}
